/**
 * LeetCode94：二叉树的中序遍历
 * 给定一个二叉树，返回它的中序遍历结果
 */

function TreeNode(val){
    this.val = val;
    this.left = this.right = null;
}

/**
 *
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root){
    if (!root){ return []; }
    const res = [];
    const rec = (n) => {
        if (!n) return;
        rec(n.left);
        res.push(n.val);
        rec(n.right);
    }
    rec(root);
    return res;
}

//时间复杂度：O(n)
//空间复杂度：O(n)